1. Technical Field
The present invention generally relates to cache memory systems and in particular to replacement policies of cache coherence systems.
2. Description of the Related Art
Caches are typically organized in a set-associative fashion, with each cache divided into a certain number of “sets”. Each set holds one or more cache-lines arranged in one or more “ways” (also referred to herein as “cache-ways”). Each cache set has Least Recently Used (LRU) bits associated with the cache set that describes the level of recent use of each cache-line within a cache set. These LRU bits are used to make replacement decisions when removing a line from a cache set, in order to make space for a new line. In addition, each cache-line may have other associated state bits. For example, if the cache participates in the coherence protocol (for example, the Modified Exclusive Shared Invalid (MESI) protocol), the cache maintains the coherence protocol state bits per cache-line.
Caches are often hierarchically organized into multiple levels, e.g., include Level 1 caches (L1) and Level 2 caches (L2). Typically, in a multi-processor system (or a processor designed with the intent of being usable in a multi-processor system), “inclusion” is maintained between cache levels. Inclusion means that all the data stored in a higher level cache is also present in a lower level cache. For example, all data in the (higher level) L1 caches are present in the (lower level) L2 cache that the L1s share. The main motivation for inclusion is that inclusion makes cache coherency easier to manage. A request from the bus may initiate an inspection/search of a lower level cache only and, as a consequence of inclusion, the search is certain to encounter any data that the higher level caches may contain.
In the example of an L2 shared by multiple L1 caches, inclusiveness requires that upon replacement of a cache line in the L2, the line is consequently invalidated in the L1s that share the L2. The invalidation of the cache-line in the L1 is called back-invalidation. Since the size of an L2 is typically much larger than the combined sizes of all the L1s that share the L2, most back-invalidation messages may end up searching the L1 for a line that the L1 does not have.
In general, the traditional cache replacement policies result in performance degrading back-invalidation caused by the policies' eviction of hot cache-lines from caches closer to cores (e.g. L1) due to back-invalidation from inclusive caches that are further from the cores (e.g. L2).